package Hot_100;

import java.util.Scanner;

//最大子数组
public class Hot_100_53 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //初始化数组
        int n = sc.nextInt();
        int arr[] = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        //调用处理函数并输出结果
        System.out.println(maxSubArray(arr));
    }

    /**
     * 求最大子数组
     *
     * @param nums
     * @return
     */
    public static int maxSubArray(int[] nums) {
        int dp[] = new int[nums.length];
        int ans = Integer.MIN_VALUE;
        //base case
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            //状态转移方程
            //dp[i] 有两种「选择」，要么与前面的相邻子数组连接，形成一个和更大的子数组；
            // 要么不与前面的子数组连接，自成一派，自己作为一个子数组。
            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
        }
        for (int i = 0; i < dp.length; i++) {
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}
//时间复杂度: O(n)
//空间复杂度: O(n)